package _11_整理题目._3_字符串_递归_dfs_bfs_双指针._子串子序列_最值;

import org.junit.Test;

/**
 * https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=117&&tqId=37799&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
 *
 * 给定两个字符串str1和str2,输出两个字符串的最长公共子串
 * 题目保证str1和str2的最长公共子串存在且唯一。
 *
 * 子串：连续的字符
 * 子序列：可以不连续
 * 
 * 滑动窗口，只会变大或不变，不会缩小
 *      
 * 
 * 动态规划
 *      
 * 
 */
public class _021_最长公共子串 {
    
    public String LCS1 (String str1, String str2) {
        String result = "";
        int start = 0, end = 1;
        while (end <= str2.length()) {
            String sub = str2.substring(start, end);
            if (str1.contains(sub)) {
                end++;
                result = sub;
            } else {
                start++;
                end++;
            }
        }
        return result;
    }
    
    public String LCS2 (String str1, String str2) {
        return "";
    }
    
    @Test
    public void main() {
        String str1 = "1AB2345CD";
        String str2 = "12345EFCD";
        assert LCS1(str1, str2).equals("2345");
    }
}
